#include <iostream>
#include "CppBTree.h"


BinaryTreeNode::BinaryTreeNode(ElementType element)
{
    this->data = element; //数据域
    this->Left = NULL;     //左孩子
    this->Right = NULL;      //右孩子
    this->parent = NULL;     //双亲
}

BinaryTreeNode::~BinaryTreeNode()
{
    this->data = NULL;
    this->Left = NULL;
    this->Right = NULL;
    this->parent = NULL;
}

BinarySortTree::BinarySortTree()
{
    this->root = NULL;
}

//判断结点高度
int BinaryTreeNode::GetNodeHeight()
{   
    int count = 0;
    if(this == NULL)
    return 0;
    int leftheight = this->Left->GetNodeHeight();
    int rightheight = this->Right->GetNodeHeight();

    return fmax(leftheight,rightheight)+1;
}


//左旋
BinaryTreeNode* BinaryTreeNode::RotateLeft()
{
    BinaryTreeNode* t = this->Right;  //定义一个指向失衡节点右孩子的指针t
    t->parent = this->parent; //将失衡点的双亲，赋给t的双亲，t成为新的根结点
    this->Right = t->Left;    //失衡点接纳t的左孩子
    t->Left = this;           //失衡点下坠，成为t新的左孩子
    this->parent = t;         //t成为失衡点新的双亲

    if(this->Right != NULL)   //失衡点接纳t的左孩子之后，将左孩子的双亲变为自己
    this->Right->parent = this;
    return t;
}

//右旋
BinaryTreeNode* BinaryTreeNode::RotateRight()
{
    BinaryTreeNode* t = this->Left;
    t->parent = this->parent;
    this->Left = t->Right;
    
    t->Right = this;
    this->parent = t;

    if(this->Left != NULL)
    this->Left->parent = this;
    return t;
}

BinaryTreeNode* BinaryTreeNode::Rotate_LeftRight()
{
    BinaryTreeNode* t = this->Left;  //定义一个指针指向失衡点的左孩子
    t = t->RotateLeft(); //把以左孩子为根节点的子树，即左子树，做左旋操作
    return this->RotateRight(); //再将整个二叉树做右旋操作
}

BinaryTreeNode* BinaryTreeNode::Rotate_RightLeft()
{
    BinaryTreeNode* t = this->Right;
    t = t->RotateRight();
    return this->RotateLeft();
}

BinaryTreeNode* BinaryTreeNode::InsertNode(BinaryTreeNode* node, ElementType element,int(*funcptr)(ElementType,ElementType))
{
    if(node == NULL)
    return node;

    //比节点小而且节点恰好没有左孩子
    if(funcptr(node->data,element) == bigger && node->Left == NULL)
    {
        node->Left = new BinaryTreeNode(element);

        if(node->Left == NULL)
            return node;
        node->Left->parent = node;
        return node;
    }

    //元素比节点大且节点恰好没有右孩子
    if(funcptr(node->data,element) == smaller && node->Right == NULL)
    {
        node->Right = new BinaryTreeNode(element);
        if(node->Right == NULL)
            return node;
        node->Right->parent = node;
        return node;
    }
    //不允许插入相同的数据,如果相同，直接返回
    if(funcptr(node->data,element) == equal)
    return NULL;

    //如果有节点存在，递归
    if(funcptr(node->data,element) == bigger)
    {
       node->Left =  InsertNode(node->Left,element,funcptr);
        //自平衡
        if(node->Left->GetNodeHeight() - node->Right->GetNodeHeight() >1)
        {
            //左左插入
            if(node->Left->data > element)
                node = node->RotateRight();   //右旋
            else
            //左右插入
                node = node->Rotate_LeftRight(); //左右旋
        }
        return node;   
    }
    else
    {
        node->Right =  InsertNode(node->Right,element,funcptr);

        if(node->Right->GetNodeHeight() - node->Left->GetNodeHeight() >1)
        {
            //右右插入
            if(node->Right->data < element)
                node = node->RotateLeft(); //左旋
            else
            //右左插入
                node = node->Rotate_RightLeft(); //右左旋
        }
        return node;
    }
}

BinaryTreeNode* BinarySortTree::InsertElement_BSTree(ElementType element,int(*funcptr)(ElementType,ElementType))
{
    if(this->root == NULL)
    {
        this->root = new BinaryTreeNode(element);
    }
    else
    {
        this->root =  this->root->InsertNode(this->root,element,funcptr);
        return this->root;
    }
    return this->root;
}

//前序遍历
void BinaryTreeNode::TravelPrev_Node(void(*funcptr)(ElementType))
{
    if(this == NULL)
        return;
    funcptr(this->data);
    this->Left->TravelPrev_Node(funcptr);
    this->Right->TravelPrev_Node(funcptr);
}

void BinarySortTree::TravelPrev_BSTree(void(*funcptr)(ElementType))
{
    this->root->TravelPrev_Node(funcptr);
}

//中序遍历
void BinaryTreeNode::TravelMid_Node(void(*funcptr)(ElementType))
{
    if(this == NULL)
        return;
    this->Left->TravelMid_Node(funcptr);
    funcptr(this->data);
    this->Right->TravelMid_Node(funcptr);
}

void BinarySortTree::TravelMid_BSTree(void(*funcptr)(ElementType))
{
    this->root->TravelMid_Node(funcptr);
}

//后序遍历
void BinaryTreeNode::TravelPost_Node(void(*funcptr)(ElementType))
{
    if(this == NULL)
        return;
    this->Left->TravelPost_Node(funcptr);
    this->Right->TravelPost_Node(funcptr);
    funcptr(this->data);
}

void BinarySortTree::TravelPost_BSTree(void(*funcptr)(ElementType))
{
    this->root->TravelPost_Node(funcptr);
}

ElementType BinaryTreeNode::GetNodeData()
{
    return this->data;
}


BinaryTreeNode* BinaryTreeNode::SearchNode(ElementType element,int(*funcptr)(ElementType,ElementType))
{
    if(this == NULL)
    {
        return NULL;
    }

    if(funcptr(this->data,element) == equal)
    return this;
    else if(funcptr(this->data,element) == smaller ) //这个节点比要找的元素小,说明元素在右边
    {
        return this->Right->SearchNode(element,funcptr); //找它的右子树

    }
    else
    {
        return this->Left->SearchNode(element,funcptr);  //否则找他的左子树

    }
}

bool BinaryTreeNode::IsLeftChild(BinaryTreeNode* parent,BinaryTreeNode* child)
{
    if(parent->Left == child)
        return true;
    else
        return false;
}


BinaryTreeNode* BinarySortTree::SearchByElement_BTNode(ElementType element,int(*funcptr)(ElementType,ElementType))
{
    return this->root->SearchNode(element,funcptr);
}

BinaryTreeNode* BinaryTreeNode::RemoveByElement(BinaryTreeNode* node,ElementType element,int(*funcptr)(ElementType,ElementType))
{
        if(node == NULL)
        return NULL;

    if(funcptr(node->data,element) == bigger)
    {
        node->Left = node->Left->RemoveByElement(node->Left,element,funcptr);

        if(this->Right->GetNodeHeight() - this->Left->GetNodeHeight() > 1)
        {
            if(this->Right->Left->GetNodeHeight() - this->Right->Right->GetNodeHeight() > 0)
            {
                node = Rotate_RightLeft();
            }
            else
            node = RotateLeft();
        }
        return node;

    }
    else if(funcptr(node->data,element) == smaller)
    {
        node->Right = RemoveByElement(node->Right,element,funcptr);

        if(node->Left->GetNodeHeight() - node->Right->GetNodeHeight() > 1)
        {
            if(node->Left->Left->GetNodeHeight() - node->Left->Right->GetNodeHeight() > 0)
            {
                node = RotateRight();
            }
            else
                node = Rotate_LeftRight();
        }
        return node;
    }
    else
    {
        //如果结点不为空，开始操作
        if(node != NULL )
        {
            BinaryTreeNode* temp = node->parent;
            //是叶子结点，左右孩子都为空
            if(node->Left == NULL && node->Right == NULL)
            {
                //如果是根结点，说明这棵树只有它一个结点
                if(node->parent == NULL)
                {
                    delete node;        //直接释放这个结点
                    node= NULL; //把根置为空
                    return temp;            //返回
                }
                //如果要删除的叶子结点，是它双亲结点的左孩子
                if(IsLeftChild(node->parent,node) == true)
                {
                    node->parent->Left = NULL;
                    delete node; 
                }
                else
                {
                    node->parent->Right = NULL;
                    delete node;
                }
                return NULL;
            }
            //要删除的结点左孩子不空，右孩子空
            else if(node->Right == NULL)
            {
                node->Left->parent = node->parent; // 直接把我的双亲当成我左孩子的双亲
                //如果是根节点
                if(node->parent == NULL)
                {
                    node = node->Left;
                    delete node;
                    return temp;
                }
                //如果是双亲节点的左孩子
                if(IsLeftChild(node->parent,node) == true)
                {
                    node->parent->Left = node->Left;
                    delete node;
                    return temp->Left;
                }
                else
                {
                    node->parent->Right = node->Left;
                    delete node;
                    return temp->Right;
                }
            }
            else if(node->Left == NULL)
            {
                node->Right->parent = node->parent; // 直接把我的双亲当成我右孩子的双亲
                //根节点
                if(node->parent == NULL)
                {
                    node = node->Right;
                    delete node;
                    return node;
                }
                //判断是左孩子还是右孩子
                if(IsLeftChild(node->parent,node) == true)
                {
                    node->parent->Left = node->Right;
                    delete node;
                    return temp->Left;
                }
                else
                {
                    node->parent->Right = node->Right;
                    delete node;
                    return temp->Right;
                }
            }
            //左右孩子都在
            else
            {
                //找右子树最小的点放过来
                BinaryTreeNode* MinNode = node->Right;
                while(MinNode->Left != NULL)
                {
                    MinNode = MinNode->Left;
                }
                node->data = MinNode->data; //把值传递给要删除的结点

                //如果右边子树的最小节点就是它本身
                if(node->Right == MinNode)
                    node->Right = MinNode->Right;
                else
                    MinNode->parent->Left = MinNode->Right;
               delete MinNode; //删除它自己
                
                return node;
            }
        }
    }
    return NULL;
}

BinaryTreeNode* BinarySortTree::GetTreeRoot()
{
    return this->root;
}

